package simpledb.util;

import java.util.*;
import java.util.stream.Collectors;

/**
 * LruCache 是一个简单的 LRU 缓存实现。
 * 它通过结合双向链表和哈希表来高效地管理缓存项，支持快速获取、插入和删除操作。
 * 当缓存达到最大容量时，会自动移除最近最少使用的项。
 */
public class LruCache<K, V> {

    // LRU 缓存节点定义
    public class Node {
        public Node pre;  // 前驱节点
        public Node next; // 后继节点
        public K    key;  // 键
        public V    value; // 值

        public Node(final K key, final V value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int          maxSize; // 最大缓存大小
    private final Map<K, Node> nodeMap; // 存储键到节点映射的哈希表
    private final Node         head;   // 双向链表的头节点（哨兵）
    private final Node         tail;   // 双向链表的尾节点（哨兵）

    /**
     * 构造函数，初始化LRU缓存。
     *
     * @param maxSize 缓存的最大容量
     */
    public LruCache(int maxSize) {
        this.maxSize = maxSize;
        this.head = new Node(null, null); // 初始化头节点
        this.tail = new Node(null, null); // 初始化尾节点
        this.head.next = tail; // 将头节点和尾节点连接起来
        this.tail.pre = head;
        this.nodeMap = new HashMap<>(); // 初始化哈希表
    }

    /**
     * 将节点链接到头部。
     *
     * @param node 要链接的节点
     */

    public void linkToHead(Node node) {
        Node next = this.head.next;
        node.next = next;
        node.pre = this.head;

        this.head.next = node;
        next.pre = node;
    }

    /**
     * 移除节点。
     *
     * @param node 要移除的节点
     */
    public void removeNode(Node node) {
        if (node.pre != null && node.next != null) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
    }

    /**
     * 将节点移动到头部。
     *
     * @param node 要移动的节点
     */
    public void moveToHead(Node node) {
        removeNode(node);
        linkToHead(node);
    }

    /**
     * 移除最后一个节点，并返回该节点。
     *
     * @return 最后一个节点
     */
    public Node removeLast() {
        Node last = this.tail.pre;
        removeNode(last);
        return last;
    }

    /**
     * 从缓存中移除指定键对应的项。
     *
     * @param key 要移除的键
     */
    public synchronized void remove(K key) {
        if (this.nodeMap.containsKey(key)) {
            final Node node = this.nodeMap.get(key);
            removeNode(node);
            this.nodeMap.remove(key);
        }
    }

    /**
     * 根据键获取对应的值。
     *
     * @param key 键
     * @return 对应的值
     */
    public synchronized V get(K key) {
        if (this.nodeMap.containsKey(key)) {
            Node node = this.nodeMap.get(key);
            moveToHead(node); // 将访问的节点移到头部
            return node.value;
        }
        return null;
    }

    /**
     * 插入或更新指定键值对。
     *
     * 如果缓存已满，则移除最近最少使用的项。
     *
     * @param key 键
     * @param value 值
     * @return 被移除的项（如果有的话）
     */
    public synchronized V put(K key, V value) {
        if (this.nodeMap.containsKey(key)) {
            Node node = this.nodeMap.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            if (this.nodeMap.size() == this.maxSize) {
                Node last = removeLast();
                this.nodeMap.remove(last.key);
                return last.value;
            }
            Node node = new Node(key, value);
            this.nodeMap.put(key, node);
            linkToHead(node);
        }
        return null;
    }

    /**
     * 返回反向迭代器（用于遍历最近最少使用的项）。
     *
     * @return 迭代器
     */
    public synchronized Iterator<V> reverseIterator() {
        Node last = this.tail.pre;
        final ArrayList<V> list = new ArrayList<>();
        while (!last.equals(this.head)) {
            list.add(last.value);
            last = last.pre;
        }
        return list.iterator();
    }

    /**
     * 返回所有值的迭代器。
     *
     * @return 迭代器
     */
    public synchronized Iterator<V> valueIterator() {
        final Collection<Node> nodes = this.nodeMap.values();
        final List<V> valueList = nodes.stream().map(x -> x.value).collect(Collectors.toList());
        return valueList.iterator();
    }

    /**
     * 获取当前缓存中的项数。
     *
     * @return 当前项数
     */
    public synchronized int getSize() {
        return this.nodeMap.size();
    }

    /**
     * 获取缓存的最大容量。
     *
     * @return 最大容量
     */
    public int getMaxSize() {
        return maxSize;
    }
}
